This invention relates to a method and apparatus for the performance of Boolean AND and Boolean OR operations on functions of two variables in which only one variable need be known. In particular, it pertains to the manipulation of data stored in a multidimensional array of memory cells. This type of multidimensional array of memory cells is utilized in the frame buffer of a computerized display, such as may be found in a computer graphics system, where the Boolean operations are performed by the pixel processor of that system.
The typical display device for a computer system, the CRT, is a raster-scanned device which has no inherent memory. The image that is to appear each time the raster is scanned must be generated by an outside source. Where this image is to be maintained on the screen, such as in a computer graphics system, the information is typically stored in a digital memory. Semiconductor memories are now low enough in cost that raster-scanned frame-buffer memories are commonly used. In a frame-buffer memory, each location in the memory corresponds to one picture element on the screen, hereinafter referred to by its common technical term "pixel". This type of memory allows the display hardware to be insensitive to the image content, an arbitrary image can be displayed by properly recording the data at each location in the frame-buffer memory. Each time the raster on the CRT is scanned, the video signal to refresh the display is generated from the memory.
FIG. 1 is a simplified block diagram of a computer graphics display system utilizing a frame-buffer memory. Host computer 102 is coupled via bidirectional bus 104 to display processor 106. The display processor 106 is couled via bidirectional bus 108 to a memory system 110. Memory system 110 is coupled via bidirectional bus 112 to video generator 114 which is coupled via bus 116 to the display 118. In a system shown in FIG. 1, the frame-buffer, here shown as memory system 110, is not directly accessible to a host computer program. Instead, the frame-buffer memory is controlled by a display processor. This processor typically appears to the host as another input-output device. In a computer graphics system, the display processor can perform graphics functions such as writing lines or inserting text characters which are part of the graphics image into the frame-buffer memory for display on the CRT. The display processor would also include the necessary memory control and rasterizing functions in order to perform these operations.
The frame-buffer 110 includes a multidimensional memory array in which each location in memory corresponds to a pixel on the screen. If it is only necessary to store the presence or absence of illumination of that particular pixel, a two-dimensional memory array is sufficient. If, however, it is desired to control the intensity of the illumination and/or the color of the illumination of that particular pixel, then a three-dimensional memory is required. In the three-dimensional memory, each location stores a word which is used to store the information to control the intensity and/or color of the pixel.
Video generator 114 reads out memory 110 in order to provide the refreshed data to the display 118 over bus 116. The video generator also includes a digital-to-analog converter to convert the digital information stored in memory 110 into an analog signal which can be used by display 118. One common form of digital-to-analog converter utilized in this type of system utilizes a look-up table in which the information stored in the frame-buffer memory 110 is used to access the location in a table stored in a digital-to-analog converter which then generates the analog output. The use of a look-up table allows for linearizing of the signal because of the non-linear nature of the digital-to-analog converter. The substitution of one look-up table for another also allows changes in the shading of an image without the need to change the information stored in the frame-buffer memory 110. Video generator 114 would also typically contain a character generator for producing text on the screen. This text would not be part of the graphics image and therefore not subject to modifications made to the graphics image. It would be used to prompt the user of the system to perform some function, for example. The text would be inserted into the displayed image by a mask-mixer which is also typically a part of the video generator. The mask-mixer, in addition to "mixing" in the text, serves to mask those portions of the memory which are not to be displayed, as in the use of double-buffered displays. This technique would typically also involve the use of a post-mask register, which is described below.
The CRT display 118 includes all the necessary power supplies and scanning circuits, as are well known to those skilled in the art.
Modification of the data stored in the memory system 110 are typically performed by two techniques known to the prior art. In one technique, the information currently contained in the memory system for that pixel is read by the processor of the display processor 106 over bus 108. This information is then combined, by Boolean operations, with the new data by the arithmetic logic unit (ALU) of the display processor and then read back to the memory. This requires a read-modify-write cycle. This technique is somtimes known as a "software" technique because the ALU of the display processor 106 is programmed to perform the necessary Boolean operations. The requirement that the system perform a read-modify-write cycle, requires 2 microseconds per pixel in a typical system.
A much faster approach is shown by the memory system 200 shown in FIG. 2. This memory system includes an ALU 212 coupled to a memory array 220 via bus 216. The memory array 220 is the frame-buffer memory 110 shown in FIG. 1. The data from the memory is read out on bus 210 into data holding register 208 which then provides this information over bus 206 into an input to ALU 212. The new information to be placed in the memory is stored in a register 202, here shown as a color register because one of the typical inputs to be added to the data stored in memory is color information. The output of color register 202 is coupled via bus 204 into another input to ALU 212. The Boolean function to be performed is input to the ALU 212 over bus 214 from means not shown. This could be another register, for example. The ALU shown in this system is wired to perform the Boolean functions directly upon decoding the desired function from the information on bus 214. Thus, although the system also requires a read-modify-write cycle, this system can operate much faster than the system shown in FIG. 1, typically 700 nanoseconds per pixel. This hardware approach of adding an additional ALU to the system, thus produces an increase in speed of almost three to one.
Several factors have made an increase in the processing speed of the pixel information necessary. First of all, CRT displays are getting larger and the pixel density on the screen, that is the number of pixels per unit length, are increasing in order to provide greater resolution on the display. Both of these factors yield larger frame-buffer memories. In addition, it has become important to be able to provide faster changes to the information displayed on the screen, in order to perform such functions as animation. The combination of larger frame-buffer memories and faster presentation of images to the screen have made the speed of processing the information per pixel an important factor.